package com.mdnote.practice.array.brackets;

/**
 * @author Rhythm-2019
 * @date 2020/10/2
 * @description 平衡括号字符串的最少插入次数
 */
public class LeetCode1541 {

    public static void main(String[] args) {
        LeetCode1541 leetCode1541 = new LeetCode1541();
        System.out.println(leetCode1541.minInsertions(")("));
    }
    public int minInsertions(String s) {
        int left_need = 0, right_need = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 遇到 （ 说明需要两个）
                right_need += 2;
                // 判断(是否为奇数，如果为奇数（如 )( ） 说明前面有一个右括号没有匹配，需要加上一个左括号和一个右括号就行了
                if (right_need % 2 == 1) {
                    left_need++;
                    right_need--;
                }
            } else {
                // 右括号
                if (right_need > 0) {
                    // 有右括号的需求
                    right_need--;
                } else {
                    // 右括号过多，要加上一个左括号和右括号
                    left_need++;
                    right_need++;
                }

            }
        }
        return left_need + right_need;
    }
}
